순열 - permutation, 조합 - combination

2023-02-08

모든 경우의 수를 구하는 게 이해가 잘 되지 않아서 정리해봤다. 탐색이 굉장히 중요한 것 같은데 매번 막히는 게 너무 답답스.. 정리가 부족한 부분이 많은 것 같아 이번 기회에 정리해보았다. 확실히 짚고 넘어가는 것도 중요하지만 반복해서 하는 게 중요한 것 같다.

순열	조합
Permutation	Combination
순서가 고려된다.	순서 고려하지 않는다.
[1, 2], [2, 1] 다른 경우로 본다.	[1, 2], [2, 1] 같은 경우로 본다.\|

permutation 구하기

function getPermutation(arr, selectNumber) {
	if (arr.selectNumber === 1) return [arr];
	// if (arr.length === 1) return [arr]; // selectNumber가 없는 경우

	const results = [];

	arr.forEach((fixed, index) => {
		const rest = [...arr.slice(0, index), ...arr.slice(index + 1)];
		// 만약 arr = [1, 2, 3, 4]일 때 index = 1, 2의 상황이라면 [2, x, x, x] 2를 앞에 fix하고 나머지 1, 3, 4를 섞어야 한다.
		// 앞의 index와 뒤의 index 수들을 합쳐 rest라는 배열을 만든다.

		const combinations = getPermutation(rest, selectNumber - 1);
		// const combinations = getPermutation(rest); // selectNumber가 없는 경우
		const attached = combinations.map((combination) => [fixed, ...item]);

		results.push(...attached);
	});

	return results;
}

배열이 [1, 2, 3, 4]일 때 재귀 함수가 작동되는 순서를 그려보면 위와 같다. 빨간색 숫자가 함수가 작동되는 순서이다. 위에서 부터 숫자를 이어보면

[1, 2, 3, 4]
[1, 2, 4, 3]
[1, 3, 2, 4]
[1, 3, 4, 2]
[1, 4, 2, 3]
[1, 4, 3, 2] …

빨간 숫자가 없는 곳도 순서는 왼쪽과 같다. 전형적인 DFS 탐색방법인 걸 확인할 수 있다.
모든 경우의 수는 4! = 4 x 3 x 2 x 1 = 24개이다.

combination 구하기

function getCombinations(arr, selectNumber) {
	if (arr.selectNumber === 1) return [arr];

	const results = [];

	arr.forEach((fixed, index) => {
		const rest = arr.slice(index + 1); // 🚀 이 부분만 위의 permutation 코드와 다르게 해주면 된다.
		// 조합은 arr = [1, 2, 3, 4]이고 index = 1, 2의 상황일 때 뒤 3, 4의 경우만 더해주면 된다.
		// 1일 때 -> 2, 3, 4의 경우 구하기
		// 2일 때 => 3, 4의 경우 구하기
		// 3일 때 => 4의 경우 구하기
		// 4일 때 => ""

		const combinations = getCombinations(rest, selectNumber - 1);
		const attached = combinations.map((combination) => [fixed, ...item]);

		results.push(...attached);
	});

	return results;
}

permutation 구하는 다른 방법들

function* permute(permutation) {
	var length = permutation.length,
		c = Array(length).fill(0),
		i = 1,
		k,
		p;

	yield permutation.slice();

	while (i < length) {
		if (c[i] < i) {
			k = i % 2 && c[i];
			p = permutation[i];
			permutation[i] = permutation[k];
			permutation[k] = p;
			++c[i];
			i = 1;
			yield permutation.slice();
		} else {
			c[i] = 0;
			++i;
		}
	}
}

// 중복 제거
function perms(arr) {
	if (!arr.length) return [[]];
	return arr.flatMap((x) => {
		// get permutations of arr without x, then prepend x to each
		return perms(arr.filter((v) => v !== x)).map((vs) => [x, ...vs]);
	});
}

// 중복 포함
function perms(arr) {
	if (!arr.length) return [[]];
	return arr.flatMap((x, i) => {
		return perms(arr.filter((v, j) => i !== j)).map((vs) => [x, ...vs]);
	});
}

function perms(arr) {
	if (!arr.length) return [[]];
	return arr.flatMap((x, i) => {
		return perms([...arr.slice(0, i), ...arr.slice(i + 1)]).map((vs) => [x, ...vs]);
	});
}

function perms(arr) {
	return arr.reduce(function permute(res, item, key, arr) {
		return res.concat(
			(arr.length > 1 &&
				arr
					.slice(0, key)
					.concat(arr.slice(key + 1))
					.reduce(permute, [])
					.map((prem) => [item].concat(perm))) ||
				item
		);
	}, []);
}

출처